package 二叉树练习题;

import java.util.Vector;

/**
 * 从树的根结点开始往下访问一直到叶子结点经过的所有结点形成一条路径。
 * 找出所有的这些路径，使其满足这条路径上所有结点数据的和等于给定的整数。
 * 例如，给定如下二叉树与整数8，满足条件的路径为6→3→-1（6+3-1=8）
 */
public class K如何在二叉树中找出与输入整数相等的所有路径 {

    /**
     * 分析与解答：可以通过对二叉树的遍历找出所有的路径，
     * 然后判断各条路径上所有结点的值的和是否与给定的整数相等，如果相等，则打印出这条路径。
     * 具体实现方法可以通过对二叉树进行先序遍历来实现，
     * 实现思路：对二叉树进行先序遍历，把遍历的路径记录下来，当遍历到叶子结点时，
     * 判断当前的路径上所有结点数据的和是否等于给定的整数，如果相等则输出路径信息。实现代码如下
     */

    public static void findRoad(BiTNode root, int num, int sum, Vector<Integer> v) {
        //记录当前遍历的root节点
        sum += root.data;
        v.add(root.data);
        //当前节点是叶子结点且遍历的路径上所有节点的和等于num
        if (root.lchild == null && root.lchild == null && sum == num) {
            for (int i = 0; i < v.size(); i++) {
                System.out.print(v.get(i) + " ");
            }
            System.out.println();
        }
        //遍历root的左子树
        if (root.lchild != null) {
            findRoad(root.lchild, num, sum, v);
        }
        //遍历root的右子树
        if (root.rchild != null) {
            findRoad(root.rchild, num, sum, v);
        }
        sum -= v.get(v.size() - 1);
        v.remove(v.size() - 1);
    }

    public static void main(String[] args) {
//        int arr[]={1,2,3,4,5,6,7,8,9};
        int arr[] = {6, 3, -1, 9, -7};
        /**
         *                          5
         *                    3           8
         *                  2   4       7   9
         *                1       6   5
         */
        BiTNode root = B如何把一个有序的整数数组放到二叉树中.arraytotree(arr, 0, arr.length - 1);
        C如何从顶部开始逐层打印二叉树结点数据.printTreeLayer(root);
        System.out.println("   ");
        Vector<Integer> s = new Vector<>();
        findRoad(root, 8, 0, s);
    }
}
